Aiming at the problem of high cost and long time consumption of updating the electronic map in navigation system, a new road judgment and electron map updating algorithm based on failure data screening was proposed, which utilized the circumstances of unsuccessful matching between the history GPS track of floating vehicle and the current electronic map. First of all, the main direction of the travel path was judged by calculating the horizontal and vertical spans of all the failure points. Secondly, elegant point screening was used to cull the misregistration groups of data points due to the malfunction of the on-board GPS equipment; then the linear least square method was used for the linear fitting of failure-matching abnormal trajectory to determine the position and direction of the track; the positioning data point groups with large error were culled by angle screening. Finally, the screened trajectory data was fused and ordered by the main direction. Combined with the road network structure of electronic map, the new road was inserted into the current road network according to the matching results of the endpoints of the new road. Experiments were conducted on the electronic map of a local area network of some city. Experimental results show that the method can accurately determine and screen the new road, and rightly insert the new road into the current network structure of the electronic map.

Traditional Dijkstra algorithm cannot adapt for the transportation network with traffic rule constraints during path planning. In order to solve this problem, based on the previous network models and algorithms, an improved Dijkstra algorithm with traffic rule constraints was proposed. It added new "to be selected state" and "renewable state" on the nodes, to solve the problem of nodes with traffic rule constraints. Meanwhile, grandfather node was introduced, thereby generating triples information of each node in the traffic network. Therefore, taking this as a backtrack basis, the shortest path from the starting node to the destination node could be obtained. This algorithm is not only applicable to the transportation network with traffic rule constraints but with low complexity. The correctness of the algorithm was verified through theoretical analysis. The effectiveness of the algorithm is verified through experimental tests carried out with actual traffic network in Chaoyang District of Changchun city and random added traffic rule constraints.